package com.wrial.kind.dp;
/*
 * @Author  Wrial
 * @Date Created in 13:31 2020/8/15
 * @Description 连续子数组的最大和
        输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
        输出: 6
        解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 */

public class MaxSubArray {
    /**
     * 使用dp来解决，dp[i]代表当前i对应的连续数组最大和
     * ans 记录当前最大的值
     * if dp[i-1]<=0  dp[i] = nums[i]
     * dp[i-1]>=0 dp[i] = dp[i-1]+nums[i]
     */
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int ans = nums[0];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = dp[i - 1] <= 0 ? nums[i] : dp[i - 1] + nums[i];
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
